//
// Created by LiuYou on 2021/12/4.
//

#include <iostream>
#include <vector>
#include <random>
#include <iterator>
#include <algorithm>


namespace sort {
    class Sort final {
    public:
        static int random(int left, int right) {
            std::random_device randomDevice;
            std::default_random_engine randomEngine( randomDevice());
            std::uniform_int_distribution<> uniformIntDistribution( left, right );
            return uniformIntDistribution( randomEngine );
        }

    public:
        // 选择排序...
        static void selectionSort(std::vector<int>& arr) {
            if (arr.empty() || arr.size() == 1) {
                return;
            }

            for (int i = 0; i < arr.size() - 1; ++i) {
                int minIndex = i;
                for (int j = i + 1; j < arr.size(); ++j) {
                    if (arr[j] < arr[minIndex]) {
                        minIndex = j;
                    }
                }
                std::swap( arr[i], arr[minIndex] );
            }
        }
        // ...选择排序

    public:
        // 冒泡排序...
        static void bubbleSortA(std::vector<int>& arr) {
            if (arr.empty() || arr.size() == 1) {
                return;
            }

            for (int i = 0; i < arr.size() - 1; ++i) {
                for (int j = arr.size() - 1; j > i; --j) {
                    if (arr[j] < arr[j - 1]) {
                        std::swap( arr[j], arr[j - 1] );
                    }
                }
            }
        }

        static void bubbleSortB(std::vector<int>& arr) {
            if (arr.empty() || arr.size() == 1) {
                return;
            }

            for (int i = arr.size() - 1; i > 0; --i) {
                for (int j = 0; j < i; ++j) {
                    if (arr[j] > arr[j + 1]) {
                        std::swap( arr[j], arr[j + 1] );
                    }
                }
            }
        }

        static void bubbleSortAOptimization(std::vector<int>& arr) {
            if (arr.empty() || arr.size() == 1) {
                return;
            }

            bool isSwap = true;
            for (int i = 0; (i < arr.size() - 1) && isSwap; ++i) {
                isSwap = false;
                for (int j = arr.size() - 1; j > i; --j) {
                    if (arr[j] < arr[j - 1]) {
                        std::swap( arr[j], arr[j - 1] );
                        isSwap = true;
                    }
                }
            }
        }

        static void bubbleSortBOptimization(std::vector<int>& arr) {
            if (arr.empty() || arr.size() == 1) {
                return;
            }

            bool isSwap = true;
            for (int i = arr.size() - 1; (i > 0) && isSwap; --i) {
                isSwap = false;
                for (int j = 0; j < i; ++j) {
                    if (arr[j] > arr[j + 1]) {
                        std::swap( arr[j], arr[j + 1] );
                        isSwap = true;
                    }
                }
            }
        }
        // ...冒泡排序

    public:
        // 插入排序...
        static void insertionSortA(std::vector<int>& arr) {
            if (arr.empty() || arr.size() == 1) {
                return;
            }

            for (int i = 1; i < arr.size(); ++i) {
                for (int j = i - 1; j >= 0; --j) {
                    if (arr[j] > arr[j + 1]) {
                        std::swap( arr[j], arr[j + 1] );
                    }
                }
            }
        }

        static void insertionSortB(std::vector<int>& arr) {
            if (arr.empty() || arr.size() == 1) {
                return;
            }

            for (int i = 1; i < arr.size(); ++i) {
                for (int j = i; j > 0; --j) {
                    if (arr[j - 1] > arr[j]) {
                        std::swap( arr[j - 1], arr[j] );
                    }
                }
            }
        }
        // ...插入排序

    public:
        // 希尔排序...
        static void shellSort(std::vector<int>& arr) {
            if (arr.empty() || arr.size() == 1) {
                return;
            }

//            for (int i = 1; i < arr.size(); ++i) {
//                for (int j = i; j > 0; --j) {
//                    if (arr[j - 1] > arr[j]) {
//                        std::swap( arr[j - 1], arr[j] );
//                    }
//                }
//            }

            for (int gap = arr.size() / 2; gap > 0; gap = gap / 2) {

                for (int i = gap; i < arr.size(); ++i) {
                    for (int j = i; /*j > 0;*/j >= gap; j = j - gap) {
                        if (arr[j - gap] > arr[j]) {
                            std::swap( arr[j - gap], arr[j] );
                        }
                    }
                }

            }

        }


        /**
         * @brief 使用 Knuth 序列的希尔排序。
         * @param arr 要排序的数组。
         *
         * @note Knuth序列:
         * h = 1;
         * h = 3 * h + 1;
         */
        static void shellSortUseKnuth(std::vector<int>& arr) {
            if (arr.empty() || arr.size() == 1) {
                return;
            }

//            for (int i = 1; i < arr.size(); ++i) {
//                for (int j = i; j > 0; --j) {
//                    if (arr[j - 1] > arr[j]) {
//                        std::swap( arr[j - 1], arr[j] );
//                    }
//                }
//            }

            int h = 1;
            while (h <= arr.size() / 3) {
                h = 3 * h + 1;
            }

            for (int gap = h; gap > 0; gap = (gap - 1) / 3) {

                for (int i = gap; i < arr.size(); ++i) {
                    for (int j = i; /*j > 0;*/j >= gap; j = j - gap) {
                        if (arr[j - gap] > arr[j]) {
                            std::swap( arr[j - gap], arr[j] );
                        }
                    }
                }

            }

        }


        // ...希尔排序
    };

}


using namespace sort;


int main(int argc, char** argv) {
    std::cout << "===================[ 选择排序 ]=====================" << std::endl;
    {
        std::vector<int> arr( 10 );
        for (auto& item: arr) {
            item = Sort::random( 0, 100 );
        }

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << " 有序: " << std::boolalpha << std::is_sorted( arr.begin(), arr.end());
        std::cout << std::endl;

        Sort::selectionSort( arr );

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << " 有序: " << std::boolalpha << std::is_sorted( arr.begin(), arr.end());
        std::cout << std::endl;
    }

    std::cout << "===================[ 冒泡排序(每次最小的冒泡到前面的位置。) ]=====================" << std::endl;
    {
        std::vector<int> arr( 10 );
        for (auto& item: arr) {
            item = Sort::random( 0, 100 );
        }

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << " 有序: " << std::boolalpha << std::is_sorted( arr.begin(), arr.end());
        std::cout << std::endl;

        Sort::bubbleSortA( arr );

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << " 有序: " << std::boolalpha << std::is_sorted( arr.begin(), arr.end());
        std::cout << std::endl;
    }

    std::cout << "===================[ 冒泡排序(每次最大的冒泡到后面的位置。) ]=====================" << std::endl;
    {
        std::vector<int> arr( 10 );
        for (auto& item: arr) {
            item = Sort::random( 0, 100 );
        }

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << " 有序: " << std::boolalpha << std::is_sorted( arr.begin(), arr.end());
        std::cout << std::endl;

        Sort::bubbleSortB( arr );

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << " 有序: " << std::boolalpha << std::is_sorted( arr.begin(), arr.end());
        std::cout << std::endl;
    }

    std::cout << "===================[ 冒泡排序(优化) ]=====================" << std::endl;
    {
        std::vector<int> arr( 10 );
        for (auto& item: arr) {
            item = Sort::random( 0, 100 );
        }

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << " 有序: " << std::boolalpha << std::is_sorted( arr.begin(), arr.end());
        std::cout << std::endl;

//        Sort::bubbleSortAOptimization( arr );
        Sort::bubbleSortBOptimization( arr );

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << " 有序: " << std::boolalpha << std::is_sorted( arr.begin(), arr.end());
        std::cout << std::endl;
    }

    std::cout << "===================[ 插入排序 ]=====================" << std::endl;
    {
        std::vector<int> arr( 10 );
        for (auto& item: arr) {
            item = Sort::random( 0, 100 );
        }

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << " 有序: " << std::boolalpha << std::is_sorted( arr.begin(), arr.end());
        std::cout << std::endl;

//        Sort::insertionSortA( arr );
        Sort::insertionSortB( arr );

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << " 有序: " << std::boolalpha << std::is_sorted( arr.begin(), arr.end());
        std::cout << std::endl;
    }

    std::cout << "===================[ 希尔排序 ]=====================" << std::endl;
    {
        std::vector<int> arr( 10 );
        for (auto& item: arr) {
            item = Sort::random( 0, 100 );
        }

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << " 有序: " << std::boolalpha << std::is_sorted( arr.begin(), arr.end());
        std::cout << std::endl;

//        Sort::shellSort( arr );
        Sort::shellSortUseKnuth( arr );

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << " 有序: " << std::boolalpha << std::is_sorted( arr.begin(), arr.end());
        std::cout << std::endl;
    }


    return 0;
}
